package.cpath = package.cpath .. ';C:/Users/win/AppData/Roaming/JetBrains/IdeaIC2020.3/plugins/intellij-emmylua/classes/debugger/emmy/windows/x86/?.dll'
local dbg = require('emmy_core')
dbg.tcpConnect('localhost', 9966)

package.path = package.path .. ";C:/Users/win/Documents/_lua/util/?.lua"

local BSTree = require("BSTree")


function Test1()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(1)
    assert(1 == bst:GetCount())
    assert(bst:Contains(1))
    assert(false == bst:Contains(0))

    bst:Add(2)
    assert(2 == bst:GetCount())
    assert(bst:Contains(2))
    assert(false == bst:Contains(0))

    bst:Add(3)
    assert(3 == bst:GetCount())
    assert(bst:Contains(3))
    assert(false == bst:Contains(0))

    bst:Add(4)
    assert(4 == bst:GetCount())
    assert(bst:Contains(4))
    assert(false == bst:Contains(0))

    assert("1,2,3,4" == tostring(bst))

    bst:Remove(1)
    assert(3 == bst:GetCount())
    assert(false == bst:Contains(1))
    assert("2,3,4" == tostring(bst))
end
Test1()


function TestRemove1()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(19)
    bst:Add(10)
    bst:Add(25)
    bst:Add(4)
    bst:Add(14)
    bst:Add(20)
    bst:Add(30)
    bst:Add(2)
    bst:Add(12)
    bst:Add(17)
    assert(10 == bst:GetCount())
    assert("19,10,25,4,14,20,30,2,12,17" == tostring(bst))

    bst:Remove(2)
    assert(9 == bst:GetCount())
    assert("19,10,25,4,14,20,30,12,17" == tostring(bst))

    bst:Add(2)
    assert(10 == bst:GetCount())
    bst:Remove(4)
    assert(9 == bst:GetCount())
    assert("19,10,25,2,14,20,30,12,17" == tostring(bst))
end
--TestRemove1()


function TestRemove2()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(19)
    bst:Add(10)
    bst:Add(25)
    bst:Add(4)
    bst:Add(14)
    bst:Add(20)
    bst:Add(30)
    bst:Add(2)
    bst:Add(12)
    bst:Add(17)
    assert(10 == bst:GetCount())
    assert("19,10,25,4,14,20,30,2,12,17" == tostring(bst))

    bst:Remove(10)
    assert(9 == bst:GetCount())
    assert("19,12,25,4,14,20,30,2,17" == tostring(bst))
end
TestRemove2()


function TestRemove3()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(19)
    bst:Add(10)
    bst:Add(25)
    bst:Add(4)
    bst:Add(14)
    bst:Add(20)
    bst:Add(30)
    bst:Add(2)
    bst:Add(12)
    bst:Add(17)
    bst:Add(11)
    bst:Add(13)
    assert(12 == bst:GetCount())
    assert("19,10,25,4,14,20,30,2,12,17,11,13" == tostring(bst))

    bst:Remove(10)
    assert(11 == bst:GetCount())
    assert("19,11,25,4,14,20,30,2,12,17,13" == tostring(bst))
end
TestRemove3()


function TestRemove4()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(19)
    bst:Add(10)
    bst:Add(25)
    bst:Add(4)
    bst:Add(14)
    bst:Add(20)
    bst:Add(30)
    bst:Add(2)
    bst:Add(12)
    bst:Add(17)
    bst:Add(13)
    assert(11 == bst:GetCount())
    assert("19,10,25,4,14,20,30,2,12,17,13" == tostring(bst))

    bst:Remove(10)
    assert(10 == bst:GetCount())
    assert("19,12,25,4,14,20,30,2,13,17" == tostring(bst))
end
TestRemove4()


function TestRemove5()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(19)
    bst:Add(10)
    bst:Add(25)
    bst:Add(4)
    bst:Add(14)
    bst:Add(20)
    bst:Add(30)
    bst:Add(2)
    assert(8 == bst:GetCount())
    assert("19,10,25,4,14,20,30,2" == tostring(bst))

    bst:Remove(10)
    assert(7 == bst:GetCount())
    assert("19,14,25,4,20,30,2" == tostring(bst))
end
TestRemove5()

function TestRemove6()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(19)
    bst:Add(10)
    bst:Add(25)
    bst:Add(4)
    bst:Add(14)
    bst:Add(20)
    bst:Add(30)
    bst:Add(2)
    bst:Add(17)
    assert(9 == bst:GetCount())
    assert("19,10,25,4,14,20,30,2,17" == tostring(bst))

    bst:Remove(10)
    assert(8 == bst:GetCount())
    assert("19,14,25,4,17,20,30,2" == tostring(bst))
end
TestRemove6()

---删除根节点
function TestRemove7()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(19)
    bst:Add(10)
    bst:Add(25)
    bst:Add(4)
    bst:Add(14)
    bst:Add(20)
    bst:Add(30)
    assert(7 == bst:GetCount())
    assert("19,10,25,4,14,20,30" == tostring(bst))

    bst:Remove(19)
    assert(6 == bst:GetCount())
    assert("20,10,25,4,14,30" == tostring(bst))
end
TestRemove7()


---删除根节点, 只有一个右孩子
function TestRemove8()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(19)
    bst:Add(10)
    bst:Add(25)
    bst:Add(4)
    bst:Add(14)
    assert(5 == bst:GetCount())
    assert("19,10,25,4,14" == tostring(bst))

    bst:Remove(19)
    assert(4 == bst:GetCount())
    assert("25,10,4,14" == tostring(bst))
end
TestRemove8()

---删除根节点, 右孩子-右孩子
function TestRemove9()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(19)
    bst:Add(10)
    bst:Add(25)
    bst:Add(4)
    bst:Add(14)
    bst:Add(30)
    assert(6 == bst:GetCount())
    assert("19,10,25,4,14,30" == tostring(bst))

    bst:Remove(19)
    assert(5 == bst:GetCount())
    assert("25,10,30,4,14" == tostring(bst))
end
TestRemove9()


---删除根节点, 右孩子-右孩子
function TestRemove10()
    local bst = BSTree.new(function(a, b)
        return a - b
    end)
    assert(0 == bst:GetCount())

    bst:Add(19)
    bst:Add(10)
    bst:Add(25)
    bst:Add(4)
    bst:Add(14)
    bst:Add(20)
    bst:Add(30)
    bst:Add(22)
    assert(8 == bst:GetCount())
    assert("19,10,25,4,14,20,30,22" == tostring(bst))

    bst:Remove(19)
    assert(7 == bst:GetCount())
    assert("20,10,25,4,14,22,30" == tostring(bst))
end
TestRemove10()